import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ghp
 * @title
 * @description
 */
class Solution {
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        // 构建sum数组
        int[][] sum = new int[row + 1][col + 1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                sum[i][j] = matrix[i - 1][j - 1] == '0' ? 0 : sum[i - 1][j] + 1;
            }
        }
        // 遍历每一层的柱子，更新max
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= row; i++) {
            // 这里就可以直接调用 【84.柱状图中最大的矩形】 的方法了
            ans = Math.max(ans, largestSquareArea(sum[i]));
        }
        return ans;
    }

    private int largestSquareArea(int[] heights) {
        // 创建一个临时数组，前0用于计算第一个柱子的面积，后一个0用于强制出栈（这一步超级重要）
        int[] tempArr = new int[heights.length + 2];
        for (int i = 1; i < heights.length + 1; i++) {
            tempArr[i] = heights[i - 1];
        }
        // 递增栈（栈中存储柱子的索引号，栈中的柱子的高度严格递增）
        Deque<Integer> stack = new ArrayDeque<>();
        int ans = 0;
        for (int i = 0; i < tempArr.length; i++) {
            while (!stack.isEmpty() && tempArr[i] < tempArr[stack.peek()]) {
                // 当前柱子的右边界已确定，可以计算已弹出柱子的面积
                int height = tempArr[stack.poll()];
                int width =  i - stack.peek() - 1;
                int side = Math.min(height, width);
                ans = Math.max(ans, side * side);
            }
            stack.push(i);
        }
        return ans;
    }
}


